//如果一个二进制字符串，是以一些 0（可能没有 0）后面跟着一些 1（也可能没有 1）的形式组成的，那么该字符串是 单调递增 的。 
//
// 给你一个二进制字符串 s，你可以将任何 0 翻转为 1 或者将 1 翻转为 0 。 
//
// 返回使 s 单调递增的最小翻转次数。 
//
// 
//
// 示例 1： 
//
// 
//输入：s = "00110"
//输出：1
//解释：翻转最后一位得到 00111.
// 
//
// 示例 2： 
//
// 
//输入：s = "010110"
//输出：2
//解释：翻转得到 011111，或者是 000111。
// 
//
// 示例 3： 
//
// 
//输入：s = "00011000"
//输出：2
//解释：翻转得到 00000000。
// 
//
// 
//
// 提示： 
//
// 
// 1 <= s.length <= 10⁵ 
// s[i] 为 '0' 或 '1' 
// 
// Related Topics 字符串 动态规划 👍 170 👎 0

package leetcode.editor.cn;
public class _926_FlipStringToMonotoneIncreasing {
    public static void main(String[] args) {
        Solution solution = new _926_FlipStringToMonotoneIncreasing().new Solution();
        String s = "00110";
//        String s = "010110";
        System.out.println(solution.minFlipsMonoIncr(s));
    }

class Solution {
    public int minFlipsMonoIncr(String s) {
        int dp0 = s.charAt(0) == '0' ? 0 : 1;
        int dp1 = s.charAt(0) == '1' ? 0 : 1;
        for (int i = 1; i < s.length(); i++) {
            int dp= Math.min(dp0, dp1);
            dp0 = dp0 + (s.charAt(i) == '1' ? 1 : 0);
            dp1 = dp + (s.charAt(i) == '0' ? 1 : 0);
        }
        return Math.min(dp0, dp1);
    }
}
    /**
     * 这个还可以优化
      */
class Solution2 {
    public int minFlipsMonoIncr(String s) {
        int[][] dp = new int[s.length()][2];
        dp[0][0] = s.charAt(0) == '0' ? 0 : 1;
        dp[0][1] = s.charAt(0) == '1' ? 0 : 1;
        for (int i = 1; i < s.length(); i++) {
            dp[i][0] = dp[i - 1][0] + (s.charAt(i) == '1' ? 1 : 0);
            dp[i][1] = Math.min(dp[i - 1][0], dp[i - 1][1]) + (s.charAt(i) == '0' ? 1 : 0);
        }
        return Math.min(dp[s.length() - 1][0], dp[s.length() - 1][1]);
    }
}
    //leetcode submit region begin(Prohibit modification and deletion)
class Solution1 {
    public int minFlipsMonoIncr(String s) {
        int count = 0;
        char[] chars = s.toCharArray();
        if (isDiZeng(chars)) return count;


        return -1;
    }

    private void huisu(char[] chars, int index) {
    }

    private boolean isDiZeng(char[] chars) {
        if (chars.length == 1) return true;
        boolean flag = false;
        for (int i = 0; i < chars.length; i++) {
            if (chars[i] == '1') {
                flag = true;
            }
            if (flag && chars[i] == '0') {
                return false;
            }
        }
        return true;
    }
}
//leetcode submit region end(Prohibit modification and deletion)

}